/*
The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 715 = 3 × 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² × 7 × 23645 = 3 × 5 × 43646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

Anser:134043
Time:1.484658527s
*/
package main

import (
	"fmt"
	"time"
)

var p = make([]int, 0, 1e3)

func main() {
	tstart := time.Now()
	prime()
	for i, count := 646, 0; ; i++ {
		if fourDistinctPrimeFactors(i) {
			count++
		} else {
			count = 0
		}
		if count >= 4 {
			fmt.Println(i - 3)
			break
		}
	}
	tend := time.Now()
	fmt.Println(tend.Sub(tstart))
}
func prime() {
	const bound = 1e6
	var s = [bound]bool{true, true}
	for i := 2; i < bound; i++ {
		for j := 2; j < bound/i; j++ {
			s[i*j] = true
		}
	}
	for k, v := range s {
		if !v {
			p = append(p, k)
		}
	}
}
func fourDistinctPrimeFactors(n int) bool {
	count := 0
	for _, i := range p {
		if n%i == 0 {
			count++
			for n%i == 0 {
				n /= i
			}
		}
		if n < i {
			break
		}
	}
	return count >= 4
}
